This present invention relates to digital data error detection and correction, and more particularly to a method and apparatus for performing error detection and correction using cyclic codes.
Cyclic codes are commonly used for digital signal error detection and error correction. Digital communication systems often employ cyclic code error correction to increase the reliability of information transmission. Digital magnetic and optical storage systems use cyclic code error correction to provide reliable storage and retrieval of data.
To create a cyclic codeword, a cyclic redundancy check (CRC) is calculated for a group of information bits. The CRC is then appended to the information bits to form a codeword, which is transmitted (or stored). A system receiving the codeword can use the CRC to detect (and correct a limited set of) errors that may have been introduced into the codeword during transmission (or storage and retrieval). The CRC thus allows corrupted codewords to be detected, and the original information bits to be recovered from a corrupted codeword in many common error situations.
Within the class of cyclic codes, BCH codes (named for Bose, Chaudhuri, and Hocquenghem, who discovered the basic properties of BCH codes) are used extensively. BCH codes are identified by their total length, n, and their information length, k, using the conventional notation BCH(n,k). For example, a BCH(15,7) code has an overall length of fifteen bits, seven of which are information bits. The remaining eight bits are CRC bits.
BCH error correction requires the calculation of one or more syndromes, both at the transmitter and at the receiver. Syndrome calculation is performed by dividing the codeword by a generator polynomial using modulo two arithmetic. The division requires one codeword shift and one codeword exclusive-or (XOR) operation for each information bit present. When the error correction technique further employs Fire code error trapping for burst error correction, additional shift and XOR operations may be required, depending upon the error location and pattern. The maximum number of additional shift and XOR operations required can be as large as the total number of bits in the codeword, minus one. The following example illustrates the steps performed in BCH burst error correction using the BCH(15,7) code.
The generator polynomial for the BCH(15,7) code is x8+x7+x6+x4+1, or 111010001. The variable x is used as a place holder. The transmit codeword CRC is calculated by first multiplying the information bits by x raised to the CRC length (in this case x8), which effectively appends a series of zeros equal in length to the CRC length, and second dividing this result by the generating polynomial. Assuming the information bits are, for example, 1001101, then the transmit codeword CRC is calculated as follows.
Multiplication by x8:       1001101    =                  x        6            +              x        3            +              x        2            +      1                          (                              x            6                    +                      x            3                    +                      x            2                    +          1                )            *              x        8              =                  x        14            +              x        11            +              x        10            +              x        8                                x        14            +              x        11            +              x        10            +              x        8              =    100110100000000  
Division by generator polynomial: 
The transmit codeword is calculated by multiplying the information bits by x raised to the CRC length and adding the CRC. In this example, the transmit codeword is: 
The BCH(15,7) code can correct any burst error up 4 bits long. Assuming the transmit codeword is subjected to the burst error pattern 000110100000000, then the receive codeword will be: 
The receiver corrects the receive codeword by first calculating the receive codeword""s syndrome, and then, in case of burst error trapping, calculating additional syndromes until the error is trapped or all possible error locations have been tested. The receive codeword""s syndrome is calculated by dividing it by the generator polynomial, as shown below for the BCH(15,7) example. 
When the receiver performs burst error correction, the syndrome is iteratively multiplied by x and divided by the generator polynomial until the error is trapped in the syndrome. The error is trapped when the most significant bits (msb""s) of the syndrome are all zero. The least significant bits (lsb""s) then contain the error pattern, and the position of the error is given by the number of iterative divisions required to trap the error. The least significant bit field length is equal to the maximum burst error length which the code can correct. The most significant bits are the remaining bits. The total number of iterative divisions which may be required is equal to the codeword length minus one, then the iterative syndromes recycle starting with the initial syndrome.
For the BCH(15,7) example, the number of msb""s is four, the number of lsb""s is four, and the total number of iterative divisions required is fourteen. The following shows how the BCH(15,7) error would be trapped. 
The error location is equal to the codeword length minus the iteration number modded with the codeword length.
error_location=(codeword_lengthxe2x88x92iteration_number)mod codeword_length
For the BCH(15,7) example above, this is equal to bit 8.
xe2x80x838=(15xe2x88x927)mod 15
The receive codeword is corrected by multiplying the error pattern by x raised to the error location and adding it to the receive codeword. 
The corrected information is then extracted from the corrected codeword.
These bit-aligned operations are inefficient for both hardware and software implementations. Hardware requires one clock cycle per shift/XOR operation. For the case of burst correction BCH(15,7), this is a total of 21 clock cycles. In many systems, the system clock is the same frequency as the bit rate, and thus only fifteen clock cycles would be available to perform the error correction for the BCH(15,7) case. Software requires one iteration loop pass per shift/XOR operation, and thus would require 21 iterations for the BCH(15,7) case. Also, software algorithms are faster if they are byte aligned rather than bit aligned. Byte alignment removes the need for shifting altogether. Thus, for both hardware and software, a faster, non-bit aligned algorithm is desirable.
In U.S. Pat. No. 3,859,630, issued Jan. 7, 1975, to Bennett, a parallel cyclic code error correction apparatus is disclosed. The apparatus of the ""630 patent accomplishes parallel cyclic encoding and decoding using read-only memory (ROM) banks instead of serial shift/XOR operations. The encoder and decoder each have a ROM bank that stores a CRC value for each possible information bit sequence. In addition, the decoder has a second ROM bank that stores an error bit pattern for each possible xe2x80x9cerror patternxe2x80x9d that can be formed by comparing a received CRC with a CRC based on the received information bits. The main drawback of this fully-parallel system is that the size of the ROM banks is impracticable for even moderately-sized cyclic coding schemes. For instance, a BCH(127,120) code would require approximately 1.33xc3x971036 ROM CRC entries in a ""630 patent implementation.
The embodiments disclosed herein provide for fast cyclic code syndrome calculation and fast burst error trapping. These embodiments utilize a set of permuted generator polynomials, each representing shifted and exclusive-ored (XORed) versions of the cyclic code generator polynomial according to a specific input bit pattern. The permuted generator polynomial may be provided by look-up table, hardware, or a software equivalent of this hardware.
In one aspect of the invention, a method for calculating a syndrome is disclosed. Considering a generator polynomial G of length g+1, capable of correcting a t-bit burst error, and an associated n-bit cyclic error correction codeword C, containing a k-bit information field, such that g=nxe2x88x92k, the method comprises the following. A shift distance m, greater than one but less than or equal to k, is pre-selected, and an iteration counter j is initialized to zero. A length-m address Aj is formed by stripping the m most significant bits (msb""s) from C. The address Aj is used to retrieve a corresponding first permuted generator polynomial. This permuted generator polynomial is then XORed with the g most significant remaining bits of C, forming a result R. Result R will, in many implementations, be fed back into the system as a new Cj of length nxe2x88x92(j*m), where j has been incremented by one to the current iteration index. If at any iteration, the new Cj contains less than m+g bits, then the new Cj is prepended with zeros to obtain the required minimum m+g length before being fed back into the system. This process is repeated until a desired result is achieved (e.g., a syndrome is calculated at R).
Codeword C can be, for example, information bits multiplied by xg or a received codeword. Codeword Cj can be, for example, an intermediate dividend of a syndrome calculation.
In a second aspect of the invention, a cyclic code error detection apparatus is disclosed. The apparatus comprises a permuted generator polynomial unit that accepts an input address and outputs, for a defined generator polynomial, a g-bit permuted generator polynomial corresponding to the input address and a shift distance m, whose value is greater than one but less than or equal to gxe2x88x92t+1. The apparatus further comprises a syndrome calculator to calculate a g-bit syndrome for a codeword using a permuted generator polynomial obtained from the permuted generator polynomial unit, for an input address comprising the m most significant bits from the codeword. The apparatus may further comprise additional elements allowing it to build codewords, detect errors in codewords, and/or trap and correct errors in codewords.